{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Padding and Stride\n",
    "\n",
    ":label:`sec_padding`\n",
    "\n",
    "\n",
    "In the previous example, our input had both a height and width of $3$\n",
    "and our convolution kernel had both a height and width of $2$,\n",
    "yielding an output representation with dimension $2\\times2$.\n",
    "In general, assuming the input shape is $n_h\\times n_w$\n",
    "and the convolution kernel window shape is $k_h\\times k_w$,\n",
    "then the output shape will be\n",
    "\n",
    "$$(n_h-k_h+1) \\times (n_w-k_w+1).$$\n",
    "\n",
    "Therefore, the output shape of the convolutional layer\n",
    "is determined by the shape of the input\n",
    "and the shape of the convolution kernel window.\n",
    "\n",
    "In several cases, we incorporate techniques,\n",
    "including padding and strided convolutions, \n",
    "that affect the size of the output.\n",
    "As motivation, note that since kernels generally \n",
    "have width and height greater than $1$,\n",
    "after applying many successive convolutions,\n",
    "we tend to wind up with outputs that are \n",
    "considerably smaller than our input.\n",
    "If we start with a $240 \\times 240$ pixel image, \n",
    "$10$ layers of $5 \\times 5$ convolutions\n",
    "reduce the image to $200 \\times 200$ pixels, \n",
    "slicing off $30 \\%$ of the image and with it \n",
    "obliterating any interesting information \n",
    "on the boundaries of the original image. \n",
    "*Padding* is the most popular tool for handling this issue.\n",
    "\n",
    "In other cases, we may want to reduce the dimensionality drastically,\n",
    "e.g., if we find the original input resolution to be unwieldy. \n",
    "*Strided convolutions* are a popular technique that can help in these instances.\n",
    "\n",
    "## Padding\n",
    "\n",
    "As described above, one tricky issue when applying convolutional layers\n",
    "is that we tend to lose pixels on the perimeter of our image.\n",
    "Since we typically use small kernels,\n",
    "for any given convolution,\n",
    "we might only lose a few pixels,\n",
    "but this can add up as we apply\n",
    "many successive convolutional layers.\n",
    "One straightforward solution to this problem\n",
    "is to add extra pixels of filler around the boundary of our input image,\n",
    "thus increasing the effective size of the image.\n",
    "Typically, we set the values of the extra pixels to $0$.\n",
    "In :numref:`img_conv_pad`, we pad a $3 \\times 3$ input,\n",
    "increasing its size to $5 \\times 5$.\n",
    "The corresponding output then increases to a $4 \\times 4$ matrix.\n",
    "\n",
    "![Two-dimensional cross-correlation with padding. The shaded portions are the input and kernel array elements used by the first output element: $0\\times0+0\\times1+0\\times2+0\\times3=0$. ](https://raw.githubusercontent.com/d2l-ai/d2l-en/master/img/conv-pad.svg)\n",
    "\n",
    ":label:`img_conv_pad`\n",
    "\n",
    "\n",
    "In general, if we add a total of $p_h$ rows of padding\n",
    "(roughly half on top and half on bottom)\n",
    "and a total of $p_w$ columns of padding\n",
    "(roughly half on the left and half on the right),\n",
    "the output shape will be\n",
    "\n",
    "$$(n_h-k_h+p_h+1)\\times(n_w-k_w+p_w+1).$$\n",
    "\n",
    "This means that the height and width of the output\n",
    "will increase by $p_h$ and $p_w$ respectively.\n",
    "\n",
    "In many cases, we will want to set $p_h=k_h-1$ and $p_w=k_w-1$\n",
    "to give the input and output the same height and width.\n",
    "This will make it easier to predict the output shape of each layer\n",
    "when constructing the network.\n",
    "Assuming that $k_h$ is even here,\n",
    "we will pad $p_h/2$ rows on both sides of the height.\n",
    "If $k_h$ is odd, one possibility is to\n",
    "pad $\\lceil p_h/2\\rceil$ rows on the top of the input\n",
    "and $\\lfloor p_h/2\\rfloor$ rows on the bottom.\n",
    "We will pad both sides of the width in the same way.\n",
    "\n",
    "Convolutional neural networks commonly use convolutional kernels\n",
    "with odd height and width values, such as $1$, $3$, $5$, or $7$.\n",
    "Choosing odd kernel sizes has the benefit\n",
    "that we can preserve the spatial dimensionality\n",
    "while padding with the same number of rows on top and bottom,\n",
    "and the same number of columns on left and right.\n",
    "\n",
    "Moreover, this practice of using odd kernels\n",
    "and padding to precisely preserve dimensionality\n",
    "offers a clerical benefit.\n",
    "For any two-dimensional array `X`,\n",
    "when the kernels size is odd\n",
    "and the number of padding rows and columns\n",
    "on all sides are the same,\n",
    "producing an output with the same height and width as the input,\n",
    "we know that the output `Y[i, j]` is calculated\n",
    "by cross-correlation of the input and convolution kernel\n",
    "with the window centered on `X[i, j]`.\n",
    "\n",
    "In the following example, we create a two-dimensional convolutional layer\n",
    "with a height and width of $3$\n",
    "and apply $1$ pixel of padding on all sides.\n",
    "Given an input with a height and width of $8$,\n",
    "we find that the height and width of the output is also $8$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "// %mavenRepo snapshots https://oss.sonatype.org/content/repositories/snapshots/\n",
    "\n",
    "%maven ai.djl:api:0.6.0\n",
    "%maven org.slf4j:slf4j-api:1.7.26\n",
    "%maven org.slf4j:slf4j-simple:1.7.26\n",
    "%maven net.java.dev.jna:jna:5.3.0\n",
    "%maven ai.djl.mxnet:mxnet-engine:0.6.0\n",
    "%maven ai.djl.mxnet:mxnet-native-auto:1.7.0-a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import ai.djl.*;\n",
    "import ai.djl.ndarray.NDArray;\n",
    "import ai.djl.ndarray.NDManager;\n",
    "import ai.djl.ndarray.index.NDIndex;\n",
    "import ai.djl.ndarray.types.Shape;\n",
    "import ai.djl.engine.*;\n",
    "import ai.djl.training.GradientCollector;\n",
    "import ai.djl.nn.Block;\n",
    "import ai.djl.nn.convolutional.Conv2D;\n",
    "import ai.djl.training.loss.Loss;\n",
    "import ai.djl.training.DefaultTrainingConfig;\n",
    "import ai.djl.training.Trainer;\n",
    "import ai.djl.training.TrainingConfig;\n",
    "import ai.djl.training.DefaultTrainingConfig;\n",
    "import ai.djl.nn.ParameterList;\n",
    "import ai.djl.training.optimizer.Optimizer;\n",
    "import ai.djl.training.optimizer.learningrate.LearningRateTracker;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "%load ../utils/plot-utils.ipynb\n",
    "%load ../utils/DataPoints.java\n",
    "%load ../utils/Training.java"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "NDManager manager = NDManager.newBaseManager();\n",
    "NDArray X = manager.randomUniform(0f, 1.0f, new Shape(1, 1, 8, 8));"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(8, 8)\n"
     ]
    }
   ],
   "source": [
    "Block block = Conv2D.builder()\n",
    "                .setKernel(new Shape(3, 3))\n",
    "                .optPad(new Shape(1, 1))\n",
    "                .optBias(false)\n",
    "                .setNumFilters(1)\n",
    "                .build();\n",
    "\n",
    "TrainingConfig config = new DefaultTrainingConfig(Loss.l2Loss());\n",
    "Model model = Model.newInstance(\"conv2D\");\n",
    "model.setBlock(block);\n",
    "\n",
    "Trainer trainer = model.newTrainer(config);\n",
    "trainer.initialize(X.getShape());\n",
    "\n",
    "NDArray yHat = trainer.forward(new NDList(X)).singletonOrThrow();\n",
    "System.out.println(yHat.getShape().slice(2));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When the height and width of the convolution kernel are different,\n",
    "we can make the output and input have the same height and width \n",
    "by setting different padding numbers for height and width."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "2"
    }
   },
   "outputs": [],
   "source": [
    "block = Conv2D.builder()\n",
    "                .setKernel(new Shape(5, 3))\n",
    "                .optPad(new Shape(2, 1))\n",
    "                .optBias(false)\n",
    "                .setNumFilters(1)\n",
    "                .build();\n",
    "\n",
    "model.setBlock(block);\n",
    "\n",
    "trainer = model.newTrainer(config);\n",
    "trainer.initialize(X.getShape());\n",
    "\n",
    "yHat = trainer.forward(new NDList(X)).singletonOrThrow();\n",
    "System.out.println(yHat.getShape().slice(2));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stride\n",
    "\n",
    "When computing the cross-correlation,\n",
    "we start with the convolution window\n",
    "at the top-left corner of the input array,\n",
    "and then slide it over all locations both down and to the right.\n",
    "In previous examples, we default to sliding one pixel at a time.\n",
    "However, sometimes, either for computational efficiency\n",
    "or because we wish to downsample,\n",
    "we move our window more than one pixel at a time,\n",
    "skipping the intermediate locations.\n",
    "\n",
    "\n",
    "We refer to the number of rows and columns traversed per slide as the *stride*.\n",
    "So far, we have used strides of $1$, both for height and width.\n",
    "Sometimes, we may want to use a larger stride.\n",
    ":numref:`img_conv_stride` shows a two-dimensional cross-correlation operation\n",
    "with a stride of $3$ vertically and $2$ horizontally.\n",
    "We can see that when the second element of the first column is output,\n",
    "the convolution window slides down three rows.\n",
    "The convolution window slides two columns to the right\n",
    "when the second element of the first row is output.\n",
    "When the convolution window slides three columns to the right on the input, \n",
    "there is no output because the input element cannot fill the window \n",
    "(unless we add another column of padding).\n",
    "\n",
    "![Cross-correlation with strides of 3 and 2 for height and width respectively. The shaded portions are the output element and the input and core array elements used in its computation: $0\\times0+0\\times1+1\\times2+2\\times3=8$, $0\\times0+6\\times1+0\\times2+0\\times3=6$. ](https://raw.githubusercontent.com/d2l-ai/d2l-en/master/img/conv-stride.svg)\n",
    "\n",
    ":label:`img_conv_stride`\n",
    "\n",
    "\n",
    "In general, when the stride for the height is $s_h$\n",
    "and the stride for the width is $s_w$, the output shape is\n",
    "\n",
    "$$\\lfloor(n_h-k_h+p_h+s_h)/s_h\\rfloor \\times \\lfloor(n_w-k_w+p_w+s_w)/s_w\\rfloor.$$\n",
    "\n",
    "If we set $p_h=k_h-1$ and $p_w=k_w-1$,\n",
    "then the output shape will be simplified to\n",
    "$\\lfloor(n_h+s_h-1)/s_h\\rfloor \\times \\lfloor(n_w+s_w-1)/s_w\\rfloor$.\n",
    "Going a step further, if the input height and width\n",
    "are divisible by the strides on the height and width,\n",
    "then the output shape will be $(n_h/s_h) \\times (n_w/s_w)$.\n",
    "\n",
    "Below, we set the strides on both the height and width to $2$,\n",
    "thus halving the input height and width."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "block = Conv2D.builder()\n",
    "                .setKernel(new Shape(3, 3))\n",
    "                .optPad(new Shape(1, 1))\n",
    "                .optStride(new Shape(2,2))\n",
    "                .optBias(false)\n",
    "                .setNumFilters(1)\n",
    "                .build();\n",
    "\n",
    "model.setBlock(block);\n",
    "\n",
    "trainer = model.newTrainer(config);\n",
    "trainer.initialize(X.getShape());\n",
    "\n",
    "yHat = trainer.forward(new NDList(X)).singletonOrThrow();\n",
    "System.out.println(yHat.getShape().slice(2));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we will look at a slightly more complicated example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "attributes": {
     "classes": [],
     "id": "",
     "n": "3"
    }
   },
   "outputs": [],
   "source": [
    "block = Conv2D.builder()\n",
    "                .setKernel(new Shape(3, 5))\n",
    "                .optPad(new Shape(0, 1))\n",
    "                .optStride(new Shape(3,4))\n",
    "                .optBias(false)\n",
    "                .setNumFilters(1)\n",
    "                .build();\n",
    "\n",
    "model.setBlock(block);\n",
    "\n",
    "trainer = model.newTrainer(config);\n",
    "trainer.initialize(X.getShape());\n",
    "\n",
    "yHat = trainer.forward(new NDList(X)).singletonOrThrow();\n",
    "System.out.println(yHat.getShape().slice(2));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For the sake of brevity, when the padding number\n",
    "on both sides of the input height and width are $p_h$ and $p_w$ respectively, we call the padding $(p_h, p_w)$.\n",
    "Specifically, when $p_h = p_w = p$, the padding is $p$.\n",
    "When the strides on the height and width are $s_h$ and $s_w$, respectively,\n",
    "we call the stride $(s_h, s_w)$.\n",
    "Specifically, when $s_h = s_w = s$, the stride is $s$.\n",
    "By default, the padding is $0$ and the stride is $1$.\n",
    "In practice, we rarely use inhomogeneous strides or padding,\n",
    "i.e., we usually have $p_h = p_w$ and $s_h = s_w$.\n",
    "\n",
    "## Summary\n",
    "\n",
    "* Padding can increase the height and width of the output. This is often used to give the output the same height and width as the input.\n",
    "* The stride can reduce the resolution of the output, for example reducing the height and width of the output to only $1/n$ of the height and width of the input ($n$ is an integer greater than $1$).\n",
    "* Padding and stride can be used to adjust the dimensionality of the data effectively.\n",
    "\n",
    "## Exercises\n",
    "\n",
    "1. For the last example in this section, use the shape calculation formula to calculate the output shape to see if it is consistent with the experimental results.\n",
    "1. Try other padding and stride combinations on the experiments in this section.\n",
    "1. For audio signals, what does a stride of $2$ correspond to?\n",
    "1. What are the computational benefits of a stride larger than $1$.\n",
    "\n",
    "## [Discussions](https://discuss.mxnet.io/t/2350)\n",
    "\n",
    "![](../img/qr_padding-and-strides.svg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "11.0.5+10-LTS"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
